home *** CD-ROM | disk | FTP | other *** search
- %OP%VS4.13 (28-Apr-92), Gerald L Fitton, R4000 5966 9904 9938
- %OP%DP0
- %OP%IRY
- %OP%PL0
- %OP%HM0
- %OP%FM0
- %OP%BM0
- %OP%LM4
- %OP%PT1
- %OP%PDPipeLine
- %OP%WC2,1250,44,1748,0,0,0,0
- %CO:A,12,72%
- %C%Recursion
- %C%by Gerald L Fitton
- Keywords:
- Recursion deref() Fitton
-
- Introduction
-
- Those of you who are following this Custom Function series will have
- read the first four articles of this series. They can be found in the
- directories Custom01, Custom02, Custom03 and Custom04.
-
- I have called the custom function language '4ProL' (this is intended to
- be short for PipeDream 4 Programming Language). Designing a new
- language such as '4ProL' is always a compromise between:
-
- (a) Including commands which provide the flexibility needed to carry
- out complex or intricate processes quickly and
-
- (b) Inherent constraints which encourage those 'good' programming
- techniques needed to facilitate debugging and program improvements.
-
- The compromise is to learn a set of conventions (a sub set of the
- constraints of the language) which encourage 'good' programming and to
- aim to write 'well written' programs. The conventions which I am
- recommending in this series have been discussed with and approved of by
- Colton Software.
-
- If you write 'good' programs using the set of conventions I recommend
- then you will be able to debug and expand your programs easily than if
- you use what I call 'bad' programming techniques.
-
- The earlier articles covered the topics Sequence (calling a function
- and returning a result), Conditional execution (If), the use of
- Parameters and Named variables, Local and Global variables and
- Repetition using For - Next loops.
-
- In this article I introduce the concept of Recursion.
-
-
- My Example
-
- For my example I am going to calculate the value of a mathematical
- function which returns the number of ways of selecting, say, a set of
- six lottery numbers from forty nine numbers or three committee members
- from a short list of ten. Although somewhat old fashioned these days,
- I shall call the function nCr because, in PipeDream and using ASCII, I
- find it difficult to use the more modern notation for this function.
-
- The value of nCr(49,6) is given by: (49*48*47*46*45*44)/(6*5*4*3*2*1).
-
- %L%You will notice that there are r (ie 6) numbers on the top
- %L%and there are r numbers on the bottom of the fraction.
-
- %L%The numbers on the top start at n (ie 49) and work downwards;
- %L%those on the bottom start at r (ie 6) and work downwards.
-
-
- Using a For - Next Loop
-
- Any program which uses recursion can also be written using either
- 'For - Next' or 'Repeat - Until' loops.
-
- One method of calculating nCr(49,6) is to work out the top line first,
- ie (49*48*47*46*45*44), then work out the bottom line, (6*5*4*3*2*1),
- finally dividing the top line by the bottom line. I don't recommend
- that method because, in some cases (but not this case) it tends to lead
- to very large numbers which might 'run off the end' of the calculator
- (ie overflow).
-
- The alternative method of calculating the value of nCr(n,r) is to start
- by calculating n/r. This is followed by multiplying the answer
- produced by (n-1)/(r-1) and then by (n-2)/(r-2) etc r times. This is
- the method I shall use since it avoids generating very large numbers
- which have to be divided by each other after calculation.
-
- %L%Load the file [nCr_1] by double clicking on it.
- %L%As well as [nCr_1] you will load the custom function file [c_nCr].
-
- Have a look at the construction of the function "binomial_1". You will
- see that, as usual, I have declared my local variable, "current_value"
- by naming it before initialising its value to 1. For the reasons I
- explained in an earlier article it is not possible to declare the
- "loop_counter" as a local variable.
-
- For the UK Weekly National Lottery (see the directory Lottery01) the
- number of possible lines is nCr(49,6) ie n = 49 and r = 6. Try these
- values in [nCr_1] and you'll see that the number of possible
- combinations of six numbers from forty nine is nCr(49,6) = ? Well?
- What is it?
-
- You'll see that I've included a dummy loop (using the loop variable
- "loop_counter_2") to slow down the operation so that you can observe
- the calculation proceeding in slot B13.
-
-
- Recurrence relationships
-
- If you look at the expression for nCr(49,6) you will see that
- nCr(49,6) = (49/6)nCr(48,5). In other words we can express the value
- of nCr(49,6) in terms of nCr(48,5). In the same way we could express
- nCr(48,5) as (48/5)nCr(47,4) and so on - but not forever!
-
- In mathematics (long before computers) this type of general statement
- existed and it is called a recurrence relationship.
-
- For the function nCr the recurrence relationship is:
-
- nCr(n,r) = (n/r)*nCr(n-1,r-1) for values of r>1.
-
- When r = 1 we have a problem because 1 - 1 = 0 and dividing by 0 is one
- of those things that mathematicians (and computers) find difficult!
-
- When r = 1 the value of nCr((n,1) = n.
-
- This leads us to a mathematical statement which we can write in
- PipeDream format as:
-
- if(r>1,nCr(n,r) = (n/r)*nCr(n-1,r-1),n)
-
-
- Using Recursion
-
- There is a lot of snobbery about recursion. It is often portrayed as a
- programming feature which can be used only by an expert.
-
- Don't you believe it!
-
- There are many useful mathematical functions (such as the nCr function
- above) which are capable of simple expression as a recurrence
- relationship but which, in explicit form, look overwhelmingly difficult
- to understand! In these cases using recursion makes the program easier
- to write and easier to understand. When a program is easy to
- understand then changing (improving or expanding) it is much easier.
- In those cases I recommend using recursion.
-
- Where the reasoning behind the use of recursion is obscure I would
- suggest that the writer is just showing off!
-
- There is a drawback to using recursion. I have to confess that
- recursion often takes longer to evaluate than the explicit (but more
- complicated) version whether you use a spreadsheet or BASIC.
-
-
- The Recursive Function
-
- Double click on the file [nCr_2]. It uses the custom function
- "binomial_2", the second function contained in the file [c_nCr].
-
- As is usual with my tutorials I have included a lot of material within
- the custom function which is not essential to its operation but which,
- I think, aids the understanding of how it all works.
-
- The recursive call is made in the line which starts
- "...set_value(answer,if . . . )". This line includes a call to the
- function "binomial_2", that is to say the function "binomial_2" calls
- itself! It is this feature of a function calling itself which makes it
- recursive.
-
- There is a difference in the arguments of the original function and the
- arguments used in the recursive call. The original function calculates
- nCr(n,r) whereas the recursive call calculates nCr(n-1,r-1).
-
- In fact, after stripping out all the non essential parts of the custom
- function nCr, what you are left with is a recursive procedure which
- expresses the fact that
-
- nCr(n,r) = (n/r)*nCr(n-1,r-1).
-
- The mathematical equation 'nCr(n,r) = (n/r)*nCr(n-1,r-1)' is a simple
- 'recurrence relationship'. Such mathematical functions are often
- expressed in BASIC or in spreadsheets as recursive functions just
- because the writing of the 'program' is easier to understand and easier
- to get right first time.
-
- I have included in the custom function "binomial_2" a block of local
- variables 'r_on_entry', 'r_on_exit' and 'entry_or_exit' with the
- intention of letting you see the recursive feature in operation.
-
- On entry each (recursive) call to the custom function is executed only
- down to the point where it becomes recursive. I call this 'entering'
- the recursive procedure because you can imagine that each time you
- reach the point of recursion you enter (go into and through) a gateway
- to the next recursion. When you go through this gateway to the next
- inner incarnation of the function PipeDream stores the 'outer' (old)
- function and displays (on screen) a new, inner incarnation of the
- custom function. You can see this happening if you observe the value
- of the local variable "r_on_entry". The early part of the function
- (down to the point of recursion) is executed recursively for reducing
- values of n and r. During this part of the recursive procedure the
- latter part of the recursive function is never executed.
-
- Naturally we can't keep going inwards for ever. When you set up a
- recursive procedure then, like everything in life, it's important to
- know when to stop! In the case of nCr we have to stop the recursive
- procedure when the value of r = 1 because the next incarnation would
- lead us to try to divide by zero.
-
- We achieve this halt to the recursion by using an if(,,) function. The
- innermost incarnation of "binomial_2" fails to call itself because the
- if(r>1,,) ceases to be true.
-
- What happens after the innermost incarnation of "binomial_2" has been
- executed? If I haven't lost you yet then you'll probably realise that
- it is the innermost incarnation of "binomial_2" which reaches the
- '...result(answer)' line before any of the 'outer' incarnations.
-
- This value is returned to the next incarnation (going outwards) which
- then completes its execution down to '...result(answer)'.
-
- Having 'entered' the recursive procedure r times we must 'unwind' it by
- using the 'exit' part of the custom function r times. You can see this
- happening by observing the value of the local variable "r_on_exit".
-
- One at a time the values of '...result(answer)' are returned until
- every incarnation has been executed. Finally the last (outermost)
- value is returned to the main spreadsheet.
-
- Also you will see that the local variable "entry_or_exit" takes
- appropriate values to show which part of the loop is being executed.
-
- So that both the 'entry' and 'exit' procedures can be observed I have
- slowed them down by using a couple of dummy For - Next loops.
-
-
- The Lottery
-
- Although I deal with the lottery in more detail in the Lottery01
- directory (on another disc) I would like to use the calculation of the
- probability of winning the fixed £10.00 prize as an example of the use
- of the obscure deref() function.
-
- The lottery machine selects six balls from the forty nine. You select
- six numbers from the forty nine. If three of your six numbers match
- three of the winning numbers then you've won £10.00.
-
- Let's consider building up our own set of six balls. We must choose
- three balls from the six winning balls. This gives nCr(6,3) possible
- combinations. We must also choose a further three from the forty six
- losers. The number of different ways of doing this is nCr(46,3).
-
- These two numbers must be multiplied together to give
- nCr(6,3)*nCr(46,3). Whatever this number is it is the number of
- different lines (of six) which win £10.00.
-
-
- DeRef(slotref)
-
- Let me use this calculation to explain something that has puzzled many
- people using the same custom function twice within the same slot.
-
- If you use the same custom function twice within the same slot then
- you'll get the wrong answer. By this I mean that if you try to
- calculate nCr(6,3)*nCr(43,3) in one slot using this version of
- "binomial_2" then you'll find that the answer you get is wrong. You'll
- get (nCr(43,3))^2 instead!
-
- The way around this problem is to use deref() as described below. I
- would classify this as a bug but it is an obscure one with an obscure
- work around. What I have to say applies to all custom functions and
- not only recursive functions - we'll use a simple custom function to
- demonstrate the effect and the work around.
-
- Double click on the file [Add] and you will load it and two similar
- custom function files [c1_Add] and [c2_Add]. Have a look at the two
- slots [Add]E2 and [Add]E3. The only difference is that slot E2 uses
- the function you'll find in [c2_Add] and E3 uses a function of the same
- name in [c1_Add]. You will appreciate that [c2_Add] gives the correct
- answer but that [c1_Add] doesn't. In fact, what the function in
- [c1_Add] does is to add [c1_Add]add_together(C3) to itself. The answer
- is always double the value in [Add]C3!
-
- The only difference between the two custom functions is that in
- [c1_Add]A13 you'll find ...result(answer) whereas in [c2_Add]A13 you'll
- find that the deref() function is included as ...result(deref(answer)).
-
- I still haven't worked out exactly why I need the deref() but I do
- remember Robert Macmillan explaining it to me once! After he'd
- explained it to me he said "You know Gerald, I think that's the first
- time I've understood the way deref() works!" He was referring to an
- application which passed an array to the custom function and returned
- another array! Often you need to use deref() in array operations if
- you wish to get the correct answer! More of this another day.
-
- You will find some (very limited) information about the deref()
- function in the PipeDream handbook but it won't tell you that you
- should use deref() as a matter of course when using custom functions
- that might be repeated within the same slot.
-
- Let's have a look at the way in which the slot [Add]E2 is evaluated and
- I'll explain my limited understanding of what is going on. During the
- first part of the calculation the custom function [c2_Add] is evaluated
- and the value of the local variable 'answer' is stored not in
- [c2_Add]B9 but in PipeDream's private workspace. Without the deref()
- function this value in the private workspace would be overwritten when
- the custom function is run the second time.
-
-
- A Double Recursion
-
- For interest only I include a BASIC program on this disc which I wrote
- originally in November 1987 called [Needles]. It is based on an
- ancient puzzle. You have to transfer a block of discs from one needle
- to another without placing a large disc on top of a smaller disc. The
- BASIC program uses the same recursive procedure, PROCmove, twice within
- itself.
-
- If you look at the parameters passed to the recursive parts of the
- procedure you'll see that it implies that a block of discs is moved
- from needle 1 to the spare needle so that the 'last' disc on needle 1
- is uncovered. After moving this last disc from needle 1 to needle 2
- the block of discs is moved from the spare needle on top of the last
- disc (now on needle 2).
-
- By defining the procedure as a recursive one we avoid worrying about
- the finer detail of moving the block of discs from needle 1 to the
- spare needle. We stop 'entering' the recursion when we have moved the
- last disc of the block we want to move.
-
- Now I'm not pretending that this is a simple problem but you might like
- to study it as an example of recursion. If you are able to find a way
- of recording the moves as a PipeDream array or spreadsheet then I'd
- like to hear from you.
-
-
- Summary
-
- Let me start by repeating advice about variables from an earlier
- article. There are three categories of variable - local variables,
- parameters and global variables.
-
- Parameters are values passed to custom functions as arguments of the
- function. The value of a parameter should not be changed within a
- custom function.
-
- Local variables are declared within a custom function using
- set_name(,). They should have no meaning outside the custom function
- in which they are used.
-
- What I have called a 'self contained' custom function is one in which
- the only variables are parameters and local variables (ie no global
- variables). Such custom functions can be use by anybody from any
- calling document (just like anybody can use the square root function)
- without knowing why it works. Furthermore, 4ProL will not get confused
- if the same name is used for local variables within different custom
- functions which are all 'working simultaneously'.
-
- A recursive custom function must be 'self contained' in the way in
- which I have described otherwise different incarnations of the custom
- function will get confused about what value to give the variable.
-
- Use the deref() function to 'disconnect' separate evaluations of the
- same custom function within a single slot (or array).
-
- You can always convert a recursive function into a for - next or
- repeat - until loop. Generally, if the function is based on a
- recurrence relationship then it is easier to write and understand the
- custom function if it is written as a recursive function mirroring the
- recurrence relationship!
-
- Many would disagree about this 'ease of writing' statement but I
- believe that is because they've not had recursive procedures explained
- to them as a way of converting a recurrence relationship such as
- nCr(n,r) = (n/r)*nCr(n-1,r-1) to a custom function. I would say,
- "First write down your 'recurrence relationship' and then write your
- recursive custom function."
-